/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-10-07
 * Time: 15:05
 */
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
//解法一：
public class PenultimateNode {
    public ListNode FindKthToTail(ListNode head,int k){
        if(head==null ||head.next==null){
            return head;
        }
        if(k<0){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1!=0){
            if(fast.next!=null){
                fast=fast.next;
                k--;
            }else{
                return null;
            }
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

//解法二：
//仅仅用一个指针进行遍历注定是没有办法很优美地实现此问题解答的，
// 所以要用两个指针，这两个指针的位置相差k-1个距离，
// 当快指针走到最后一个节点的时候，慢指针指向的位置就是我们要的倒数第k个节点了
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k ==0 ){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        //fast先走k-1步
        for(int i=1;i<=k;i++){
            if(fast==null){
                return null;
            }
            fast=fast.next;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;//fast走到最后一个节点

    }
}
}
